package com.sheng.leetcode.year2023.month08.day23;

import lombok.var;
import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @author by ls
 * @date 2023/8/23
 * <p>
 * 1782. 统计点对的数目<p>
 * <p>
 * 给你一个无向图，无向图由整数 n  ，表示图中节点的数目，和 edges 组成，<p>
 * 其中 edges[i] = [ui, vi] 表示 ui 和 vi 之间有一条无向边。同时给你一个代表查询的整数数组 queries 。<p>
 * 第 j 个查询的答案是满足如下条件的点对 (a, b) 的数目：<p>
 * a < b<p>
 * cnt 是与 a 或者 b 相连的边的数目，且 cnt 严格大于 queries[j] 。<p>
 * 请你返回一个数组 answers ，其中 answers.length == queries.length 且 answers[j] 是第 j 个查询的答案。<p>
 * 请注意，图中可能会有 重复边 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：n = 4, edges = [[1,2],[2,4],[1,3],[2,3],[2,1]], queries = [2,3]<p>
 * 输出：[6,5]<p>
 * 解释：每个点对中，与至少一个点相连的边的数目如上图所示。<p>
 * <p>
 * 示例 2：<p>
 * 输入：n = 5, edges = [[1,5],[1,5],[3,4],[2,5],[1,3],[5,1],[2,3],[2,5]], queries = [1,2,3,4,5]<p>
 * 输出：[10,10,9,8,6]<p>
 * <p>
 * 提示：<p>
 * 2 <= n <= 2 * 10^4<p>
 * 1 <= edges.length <= 10^5<p>
 * 1 <= ui, vi <= n<p>
 * ui != vi<p>
 * 1 <= queries.length <= 20<p>
 * 0 <= queries[j] < edges.length<p>
 */
public class LeetCode1782 {

    @Test
    public void test01() {
        int n = 4;
        int[][] edges = {{1, 2}, {2, 4}, {1, 3}, {2, 3}, {2, 1}};
        int[] queries = {2, 3};
//        int n = 5;
//        int[][] edges = {{1, 5}, {1, 5}, {3, 4}, {2, 5}, {1, 3}, {5, 1}, {2, 3}, {2, 5}};
//        int[] queries = {1, 2, 3, 4, 5};
        System.out.println(Arrays.toString(new Solution().countPairs(n, edges, queries)));
    }
}

class Solution {
    public int[] countPairs(int n, int[][] edges, int[] queries) {
        // deg[i] 表示与点 i 相连的边的数目
        var deg = new int[n + 1]; // 节点编号从 1 到 n
        var cntE = new HashMap<Integer, Integer>();
        for (var e : edges) {
            int x = e[0], y = e[1];
            // 将小的点放到左边
            if (x > y) {
                // 交换 x 和 y，因为 1-2 和 2-1 算同一条边
                int tmp = x;
                x = y;
                y = tmp;
            }
            // 累加点 x 和点 y 出现的次数
            deg[x]++;
            deg[y]++;
            // 统计每条边的出现次数
            // 用一个 int 存储两个不超过 65535 的数
            cntE.merge(x << 16 | y, 1, Integer::sum); // cntE[x<<16|y]++
        }

        var ans = new int[queries.length];
        var sortedDeg = deg.clone();
        Arrays.sort(sortedDeg); // 排序，为了双指针
        for (int j = 0; j < queries.length; j++) {
            int q = queries[j];
            int left = 1, right = n; // 相向双指针
            while (left < right) {
                if (sortedDeg[left] + sortedDeg[right] <= q) {
                    left++;
                } else {
                    ans[j] += right - left;
                    right--;
                }
            }
            for (var e : cntE.entrySet()) {
                int k = e.getKey(), c = e.getValue();
                int s = deg[k >> 16] + deg[k & 0xffff]; // 取出 k 的高 16 位和低 16 位
                if (s > q && s - c <= q) {
                    ans[j]--;
                }
            }
        }
        return ans;
    }
}
